
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Introduction to CRF(1) - Into Data</title>
  <meta name="author" content="Haipeng Liu">

  
  <meta name="description" content="Author: Haipeng Liu email to me
keywords: CRF Sequential labelling problem Conditional random field is proposed to model the sequence data. The &hellip;">
  

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://haipengliu.github.io/blog/2014/11/15/my-first-blog">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Into Data" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="./javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.googleapis.com/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.googleapis.com/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">

<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript"
   src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Into Data</a></h1>
  
    <h2>data, code, algorithm. A developer&#8217;s blog.</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="q" value="site:haipengliu.github.io" />
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Start</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">Introduction to CRF(1)</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2014-11-15T08:55:38+08:00'><span class='date'><span class='date-month'>Nov</span> <span class='date-day'>15</span><span class='date-suffix'>th</span>, <span class='date-year'>2014</span></span> <span class='time'>8:55 am</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><p>Author: Haipeng Liu <A href="mailto:pliu1981@gmail.com">email to me</A></br>
keywords: CRF</br></p>

<h1>Sequential labelling problem</h1>

<p><strong>Conditional random</strong> field is proposed to model the sequence data. The sequence data are the data or objects with a sequence structure.
For example, in Noun-Phrase (NP) chunking task, for a sentence, we want to provide correct phrasal labels for each word. The phrasal labels are B-NP for the beginning words of a noun-phrase, I-NP for the words inside a noun-phase and O for others. For instant, a labelled sentence in the CoNLL2000 dataset reads like this.</p>

<blockquote><p>Chancellor/O of/O the/B-NP Exchequer/I-NP Nigel/B-NP Lawson/I-NP &rsquo;s/B-NP restated/I-NP commitment/I-NP to/O a/B-NP firm/I-NP monetary/I-NP policy/I-NP has/O helped/O to/O prevent/O a/B-NP freefall/I-NP in/O sterling/B-NP over/O the/B-NP past/I-NP week/I-NP ./O</p></blockquote>

<p><em>CoNLL2000</em></p>

<p>The CRF can automatically label the noun phrase character as the human does</p>

<h1>Model the sequence</h1>

<p>To model the labeling process. We use $x$ to denote the labels and $z$ to denote the data. In our case $x$ is the sequence of noun phrase labels and $z$ is the sequence of words. $t$ is the sequence index. Also, $x$ is named hidden state variables, $z$ is named the observations. The task of CRF is to predict the state variables given the observations. That is to compute the probability:
   <!-- more --> <br/>
$P(x|z)$, where $x = (x_1, x_2, &hellip;, x_T)$ the labels, $z$ the data, $t\in[1, T]$ sequence index.</p>

<h1>Potential functions</h1>

<p>With the theory of undirected Markov chain, the conditional probability of $x$ given $z$ is defined as the product of a serial potential functions. Where:</br></p>

<p>$$P(x|z) = \frac{1}{Z(z)}\sum_{c}\psi_c(x_c, z)$$
$\psi_c(x_c, z)$ - potential function&lt;\br>
$Z(z) = \sum_x\prod_c\psi_c(x_c, z)$ - partition function&lt;\br></p>

<p> $\psi$ are positive functions known as potentials.</br>
 $Z(z)$ is the normalization constant known as the partition function, which guarantees the formula return a value in the range from zero to one. It’s the sum of the potentials but accounting for all the possible x values, which can be treated as the edge probabilities along side the $x$. </br>
 The number of potentials is denoted by $c$. Here in undirected Markov chain, $c$ stands for clique, which means different connections among nodes. In CRF, generally there are two kinds of connections, one is the current node connecting observation nodes, another is the nearby two nodes connecting observations nodes. They are corresponded to two kinds of potentials – <strong>node potential</strong> and <strong>edge potential</strong>.</p>

<blockquote><p>Two types of potentials</br>
node potential of label $x_t$ at time $t$</p></blockquote>

<p>$$\begin{equation}\phi_t(x_t, z) = exp(\sum_k\omega_kf_k(x_t, z, t))\dots\end{equation}~Eq.(1)\dots~a~S\times{}T~matrix$$</p>

<blockquote><p>edge potential of two nearby labels at time $t$ and $t+1$</p></blockquote>

<p>$$\begin{equation}\varphi_t(x_t, x_t+1, z) = exp(\sum_k\omega_kf_k(x_t, x_t+1, z_t))\dots\end{equation}~Eq.(2)\dots~a~S\times{}S\times{}T~matrix$$</p>

<p>The concept of potentials can be imagined as energies. Those local, nearby pieces of energies are used to compose the probability. The potentials refer to some quantities that tie the labels and the local data patterns at particular time together. In the simplest case which is often used in practice, potentials are exponential of sum of weighted features. There are usually two types of potential functions: node potential functions and edge potential functions, according to different clique styles they are connected.</p>

<p>The node potential $\phi$ describes the contribution of the current node and its connecting observations to the global model. The edge potential $\varphi_t$ describes the contribution of two nearby labels and their connecting observations to the global model. The connecting styles between nodes and observations are modeled by feature functions. Where $f_k$ is called the feature function, $\omega_k$ is the weight for a feature and $k$ is the number of features. Feature functions connect the labels and the observed data. There may be S labels and T observations. So each potential function is a multi-dimensionl matrix.</p>

<p>The node potential can be represented by a $S\times{}T$ matrix ($S$ stands for the number of labels and $T$ stands for the number of input items. The edge potential can be implemented as an $S\times{}S\times{}T$ matrix.
Since we have two type of potentials, then we can get two type of features.</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Haipeng Liu</span></span>

      




<time class='entry-date' datetime='2014-11-15T08:55:38+08:00'><span class='date'><span class='date-month'>Nov</span> <span class='date-day'>15</span><span class='date-suffix'>th</span>, <span class='date-year'>2014</span></span> <span class='time'>8:55 am</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/crf/'>crf</a>, <a class='category' href='/blog/categories/machine-learning/'>machine learning</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  <a href="//twitter.com/share" class="twitter-share-button" data-url="http://haipengliu.github.io/blog/2014/11/15/my-first-blog/" data-via="" data-counturl="http://haipengliu.github.io/blog/2014/11/15/my-first-blog/" >Tweet</a>
  
  
  
</div>

    
    <p class="meta">
      
      
        <a class="basic-alignment right" href="/blog/2014/11/18/introduction-to-crf-2/" title="Next Post: Introduction to CRF(2)">Introduction to CRF(2) &raquo;</a>
      
    </p>
  </footer>
</article>

  <section>
    <h1>Comments</h1>
    <div id="disqus_thread" aria-live="polite"><noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
  </section>

</div>

<aside class="sidebar">
  
    <section>
  <h1>About Me</h1>
  <p>Haipeng Liu</p>
  <p>Currently working in Beijing China</p>
  <p>Major research area is Natural Language Processing and Machine Learning.</p>
  <p>Love coding and like to share my thoughts and ideas with you.</p>
  
  <p>Contact me at pliu1981 # gmail.com</p>
</section>
<section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2014/12/23/how-to-use-octopress-to-write-blog/">How to Use Octopress to Write Blog on Github</a>
      </li>
    
      <li class="post">
        <a href="/blog/2014/11/18/introduction-to-crf-2/">Introduction to CRF(2)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2014/11/15/my-first-blog/">Introduction to CRF(1)</a>
      </li>
    
  </ul>
</section>




<section> 
  <h1>Categories</h1> 
  <ul id="categories"> 
    <li class='category'><a href='/blog/categories/blog/'>blog (1)</a></li>
<li class='category'><a href='/blog/categories/crf/'>crf (2)</a></li>
<li class='category'><a href='/blog/categories/machine-learning/'>machine learning (2)</a></li>
<li class='category'><a href='/blog/categories/octopress/'>octopress (1)</a></li>
 
  </ul> 
</section>

  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><p>
  Copyright &copy; 2014 - Haipeng Liu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>

</footer>
  

<script type="text/javascript">
      var disqus_shortname = 'haipengliu';
      
        
        // var disqus_developer = 1;
        var disqus_identifier = 'http://haipengliu.github.io/blog/2014/11/15/my-first-blog/';
        var disqus_url = 'http://haipengliu.github.io/blog/2014/11/15/my-first-blog/';
        var disqus_script = 'embed.js';
      
    (function () {
      var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
      dsq.src = '//' + disqus_shortname + '.disqus.com/' + disqus_script;
      (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
    }());
</script>







  <script type="text/javascript">
    (function(){
      var twitterWidgets = document.createElement('script');
      twitterWidgets.type = 'text/javascript';
      twitterWidgets.async = true;
      twitterWidgets.src = '//platform.twitter.com/widgets.js';
      document.getElementsByTagName('head')[0].appendChild(twitterWidgets);
    })();
  </script>





</body>
</html>
